import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet;

public class t1071 {
    //1071. 字符串的最大公因子 简单
    public static void main(String[] args) {
        //答案必是某个串的前子串
        //优化：子串长度为两串的最大公因数
        String str1 = "ABABAB";
        String str2 = "ABAB";
        System.out.println(gcdOfStrings(str1, str2));
        //System.out.println(gcdOfStrings(str1, str2));
        // System.out.println((int)'A');
    }

    public static String gcdOfStrings(String str1, String str2) {
        int len1 = str1.length(), len2 = str2.length();
        System.out.println(gcd(len1, len2));
        String X = str1.substring(0,gcd(len1,len2));
        System.out.println(X);
        if (check(str1,X)&&check(str2,X)) {
            return X;
        }
        return "";
        //先寻找最长的公共子串
        //检验能否全部消除
        //不能就换下一个次长字串
//        List<String> list = new ArrayList<>();
//        char[] c1 = str1.toCharArray();
//        char[] c2 = str2.toCharArray();
//        int i = 0;
//        int j = 0;
//        String str = "";
//        while (i < c1.length) {
//            int tmp = i;
//            while (tmp < c1.length && j < c2.length) {
//                if (c1[tmp] == c2[j]) {
//                    str += c2[j];
//                    tmp++;
//                    j++;
//                } else {
//                    j++;
//                }
//            }
//            if (str.length() > 0) {
//                list.add(str);
//            }
//            str = "";
//            j = 0;
//            i++;
//        }
//        //list包含了所有可能
//        // list.forEach(s-> System.out.println(s));
//        String ss = "";
//        for (String s : list) {
//            if (check(str1, s) && check(str2, s)) {
//                int max = Math.max(ss.length(), s.length());
//                if (ss.length() == max) {
//                    continue;
//                }
//                if (s.length() == max) {
//                    ss = s;
//                }
//            }
//        }
//        return ss;

    }
    //辗转相除法求最大公因数
    public static int gcd(int a,int b){
        int num = a%b;
        while (num!=0) {
            a = b;
            b = num;
            num = a % b;
        }
        return b;
    }
    public static boolean check(String str, String X) {
        if (str.contains(X)) {
          str = str.replace(X,"");
          if(str.length()==0){
              return true;
          }
        }
        return false;
    }
}
